home *** CD-ROM | disk | FTP | other *** search
/ Whiteline: Alpha / Whiteline Alpha.iso / progtool / modula2 / modprint / hashtabl.mod < prev    next >
Encoding:
Modula Implementation  |  1994-09-22  |  3.7 KB  |  158 lines
  1. IMPLEMENTATION MODULE HashTable;
  2.  
  3. (*
  4.  * This module implements a hash table with strings as keys.  
  5.  * It could easily be modified to have additional elements.
  6.  *
  7.  * Usage assumptions:
  8.  * The calling module MUST have created a heap before calling these routines!!
  9.  *
  10.  *    Copyright 1987, Barry Locklear
  11.  *
  12.  *    The author grants the privilege of distributing this
  13.  *    software free, or for a nominal charge to cover the media
  14.  *    costs, or for connect time.  
  15.  *
  16.  *    Distribution for commercial gain is prohibited.
  17.  * 
  18.  *    The only exception is that Jefferson Software may
  19.  *    distribute it with their Modula-2 package if they so
  20.  *    desire.
  21.  *
  22.  *    If improvements are made, please send them to me.
  23.  *    Compuserve: 76327,2102
  24.  *    Genie:      BLOCKLEAR
  25.  *      The Jefferson Software BBS (602)276-6102
  26.  *
  27.  *    This MODULE is written in Jefferson Software Modula-2
  28.  *)
  29.  
  30. FROM Heap     IMPORT ALLOCATE, DEALLOCATE;
  31. FROM String     IMPORT Assign, Compare, GetTerminator, Equal;
  32. FROM SYSTEM     IMPORT TSIZE;
  33.  
  34. IMPORT Terminal;
  35.  
  36. CONST
  37.  HASHTABLESIZE = 29;    (* number of hash table buckets *)
  38.  
  39. TYPE
  40.  EntryPtr  = POINTER TO HashEntry;
  41.  
  42.  HashEntry = RECORD
  43.               HashEntry : ARRAY [0..14] OF CHAR;
  44.           HashVal   : CARDINAL;
  45.           NextEntry : EntryPtr;
  46.          END;
  47.  
  48. VAR
  49.  HashTableArray : ARRAY [0..HASHTABLESIZE-1] OF EntryPtr;
  50.  index : INTEGER;
  51.  
  52. (* --------------------------------------------------------------------*)
  53.  
  54. (*
  55.  * Calculates a hash value using the very simple method of adding
  56.  * the values of the characters in the string.
  57.  *)
  58. PROCEDURE CalcHashVal( Str : ARRAY OF CHAR ) : CARDINAL;
  59.  VAR
  60.   index      : INTEGER;
  61.   hashVal    : CARDINAL;
  62.   stringTerm : CHAR;
  63.  
  64. BEGIN
  65.  hashVal := 0;
  66.  index := 0;
  67.  stringTerm := GetTerminator();
  68.  
  69.  LOOP
  70.         IF (index > HIGH(Str)) OR (Str[ index ] = stringTerm)
  71.     THEN EXIT; 
  72.     END; (* IF *)
  73.  
  74.     (* ORD is supposed to return a CARDINAL value!!!! *)
  75.         (* see page 162 of the third ed. of Wirth's book *)
  76.     hashVal := hashVal + VAL( CARDINAL, ORD(Str[index]));
  77.     INC( index );
  78.  END; (* LOOP *)
  79.  
  80.  RETURN hashVal; 
  81. END CalcHashVal;
  82.  
  83. (* --------------------------------------------------------------------*)
  84.  
  85. (*
  86.  * Inserts an element into the hash table
  87.  *)
  88. PROCEDURE InsertElem( Elem : ARRAY OF CHAR );
  89.  
  90. VAR
  91.   newEntryPtr  : EntryPtr;
  92.  
  93.   hashIndex,
  94.   hashVal      : CARDINAL;
  95.  
  96. BEGIN
  97.  hashVal := CalcHashVal( Elem );
  98.  hashIndex := hashVal MOD HASHTABLESIZE;
  99.  
  100.  (*
  101.   * allocate the entry and fill it up
  102.   *)
  103.  ALLOCATE( newEntryPtr, TSIZE( HashEntry ));
  104.  
  105.  IF newEntryPtr = NIL THEN
  106.      Terminal.WriteString("ModPrint: Out of Memory!"); Terminal.WriteLn;
  107.      RETURN;
  108.  END; (* IF *)
  109.  
  110.  Assign( newEntryPtr^.HashEntry, Elem );
  111.  
  112.  newEntryPtr^.HashVal := hashVal;
  113.  
  114.  (*
  115.   * Now insert the new entry into the table
  116.   *)
  117.  newEntryPtr^.NextEntry := HashTableArray[ hashIndex ];
  118.  HashTableArray[ hashIndex ] := newEntryPtr;
  119.  
  120. END InsertElem;
  121.  
  122. (* --------------------------------------------------------------------*)
  123.  
  124. (*
  125.  * Lookup an entry in the table to see if it is there
  126.  *)
  127. PROCEDURE LookupElem( Entry : ARRAY OF CHAR ) : BOOLEAN;
  128.  
  129.  VAR
  130.   hashVal, 
  131.   hashIndex : CARDINAL;
  132.   walkPtr   : EntryPtr;
  133.  
  134. BEGIN
  135.  hashVal := CalcHashVal( Entry );
  136.  hashIndex := hashVal MOD HASHTABLESIZE;
  137.  walkPtr := HashTableArray[ hashIndex ];
  138.  
  139.  WHILE walkPtr <> NIL DO
  140.    IF hashVal = walkPtr^.HashVal THEN
  141.       IF Compare( Entry, walkPtr^.HashEntry ) = Equal THEN
  142.          RETURN TRUE;
  143.       END; (* IF *)
  144.    END; (* IF *)
  145.    walkPtr := walkPtr^.NextEntry;
  146.  END; (* WHILE *)
  147.  
  148.  RETURN FALSE;
  149.  
  150. END LookupElem;
  151.  
  152. BEGIN
  153.  (* Make certain that the table is NIL *)
  154.  FOR index := 0 TO HASHTABLESIZE-1 DO 
  155.   HashTableArray[ index ] := NIL; 
  156.  END; (* FOR *)
  157. END HashTable.
  158.